Rearrange string k distance apart [Greedy, Heap]

Time: O(N); Space: O(N); hard

Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string “”.

Example 1:

Input: s = “aabbcc”, k = 3

Output: “abcabc”

Explanation:

• The same letters are at least distance 3 from each other.

Example 2:

Input: s = “aaabc”, k = 3

Output: “”

Explanation:

• It is not possible to rearrange the string.

Example 3:

Input: s = “aaadbbcc”, k = 2

Output: “abacabcd”

Explanation:

• The same letters are at least distance 2 from each other.

1. Greedy [O(N), O(N)]

class Solution1(object):
    """
    Time: O(N)
    Space: O(N)
    """
    def rearrangeString(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        cnts = [0] * 26
        for c in s:
            cnts[ord(c) - ord('a')] += 1

        sorted_cnts = []
        for i in range(26):
            sorted_cnts.append((cnts[i], chr(i + ord('a'))))
        sorted_cnts.sort(reverse=True)

        max_cnt = sorted_cnts[0][0]
        blocks = [[] for _ in range(max_cnt)]
        i = 0
        for cnt in sorted_cnts:
            for _ in range(cnt[0]):
                blocks[i].append(cnt[1])
                i = (i + 1) % max(cnt[0], max_cnt - 1)

        for i in range(max_cnt-1):
            if len(blocks[i]) < k:
                return ''

        return ''.join(map(lambda x : ''.join(x), blocks))

sol = Solution1()

s = "aabbcc"
k = 3
# print(sol.rearrangeString(s, k))
assert sol.rearrangeString(s, k) == "abcabc" or "cbacba"

s = "aaabc"
k = 3
assert sol.rearrangeString(s, k) == ""

s = "aaadbbcc"
k = 2
# print(sol.rearrangeString(s, k))
assert sol.rearrangeString(s, k) == "abacabcd" or "acbdacba"

2. Heap

from collections import Counter
from heapq import heappush, heappop

class Solution2(object):
    def rearrangeString(self, s, k):
        """
        :type str: str
        :type k: int
        :rtype: str
        """
        if k <= 1:
            return s

        cnts = Counter(s)
        heap = []
        for c, cnt in cnts.items():
            heappush(heap, [-cnt, c])

        result = []
        while heap:
            used_cnt_chars = []
            for _ in range(min(k, len(s) - len(result))):
                if not heap:
                    return ''
                cnt_char = heappop(heap)
                result.append(cnt_char[1])
                cnt_char[0] += 1
                if cnt_char[0] < 0:
                    used_cnt_chars.append(cnt_char)
            for cnt_char in used_cnt_chars:
                heappush(heap, cnt_char)

        return ''.join(result)

sol = Solution2()

s = "aabbcc"
k = 3
# print(sol.rearrangeString(s, k))
assert sol.rearrangeString(s, k) == "abcabc" or "cbacba"

s = "aaabc"
k = 3
assert sol.rearrangeString(s, k) == ""

s = "aaadbbcc"
k = 2
# print(sol.rearrangeString(s, k))
assert sol.rearrangeString(s, k) == "abacabcd" or "acbdacba"

See also:

https://leetcode.com/problems/rearrange-string-k-distance-apart

https://www.lintcode.com/problem/rearrange-string-k-distance-apart/description